package zuochengyun;

//丢旗子问题，k颗棋子丢N层楼，求在最坏情况下判断不会摔坏的最高层数的丢旗子的次数
public class DiuQiZhiProblem {

	//采用动态规划的方式来求解
	public int solution2(int nLevel, int kChess){
		if(nLevel < 1 || kChess < 1){
			return 0;
		}
		if(kChess == 1){
			return nLevel;
		}
		//dp[i][j]表示i层j个棋子所需的最小次数
		int[][] dp = new int[nLevel + 1][kChess + 1];
		
		//初始化，当只有一个棋子时，始终需要一层一层试，所以返回i
		for (int i = 0; i < dp.length; i++) {
			dp[i][1] = i;
		}
		//递推方程为dp[i][j] = min{max{dp[k - 1][j - 1], dp[i - k][j]}(1 =< k <= N)} + 1
		//含义为首先在第k层试验，如果碎了(此时棋子少了一颗)，试验0...k - 1层。否则实验k + 1 ... i层即可
		for(int i = 1; i < dp.length; i++){
			for (int j = 2; j < dp[0].length; j++) {
				int min = Integer.MIN_VALUE;
				for (int k = 1; k <= i; k++) {
					min = Math.min(min, Math.max(dp[k - 1][j - 1], dp[i - k][j]));
				}
				dp[i][j] = min + 1;
			}
		}
		return dp[nLevel][kChess];
	}
	
	
	//采用四边形不等式进行优化
	public int solution4(int nLevel, int kChess){
		if(nLevel < 1 || kChess < 1){
			return 0;
		}
		if(kChess == 1){
			return nLevel;
		}
		//dp[i][j]表示i层j个棋子所需的最小次数
		int[][] dp = new int[nLevel + 1][kChess + 1];
		//初始化，当只有一个棋子时，始终需要一层一层试，所以返回i
		for (int i = 0; i < dp.length; i++) {
			dp[i][1] = i;
		}
		
		int[] cands = new int[kChess + 1];
		for (int i = 0; i < dp[0].length; i++) {
			dp[1][i] = 1;
			cands[i] = 1;
		}
		
		//递推方程为dp[i][j] = min{max{dp[k - 1][j - 1], dp[i - k][j]}(1 =< k <= N)} + 1
		//含义为首先在第k层试验，如果碎了(此时棋子少了一颗)，试验0...k - 1层。否则实验k + 1 ... i层即可
		for(int i = 1; i < dp.length; i++){
			for (int j = 2; j < dp[0].length; j++) {
				int min = Integer.MIN_VALUE;
				int minNum = cands[j];
				int maxNum = j == kChess ? i / 2 + 1 : cands[j + 1];
				for (int k = minNum; k <= maxNum; k++) {
					int cur = Math.max(dp[k - 1][j - 1], dp[i - k][j]);
					if(cur <= min){
						min = cur;
						cands[j] = k;
					}
				}
				dp[i][j] = min + 1;
			}
		}
		return dp[nLevel][kChess];
	}
}
